package number_131;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    private List<List<String>> res;
    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        LinkedList<String> list = new LinkedList<>();
        backTrace(1, s, list);
        return res;
    }

    private void backTrace(int index, String word, LinkedList<String> list) {
        if (index > word.length()) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = index; i <= word.length(); i++) {
            if (isPalindrome(word.substring(0, i))) {
                list.add(word.substring(0, i));
                backTrace(1, word.substring(i, word.length()), list);
                list.removeLast();
            }
        }
    }

    private boolean isPalindrome(String substring) {
        return substring.equals(new StringBuffer(substring).reverse().toString());
    }

    public static void main(String[] args) {
        new Solution().partition("aab");
    }
}
